package com.hyper_yang.algorithmRecord.pathfinder;

import java.util.*;

class Node implements Comparable<Node> {
    int r;
    int c;
    int gCost;
    int hCost;
    int fCost;
    Node parent; // 存储父节点

    public Node(int r, int c, int gCost, int hCost, Node parent) {
        this.r = r;
        this.c = c;
        this.gCost = gCost;
        this.hCost = hCost;
        this.fCost = gCost + hCost;
        this.parent = parent; // 这里设置了父节点
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.fCost, other.fCost);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return r == node.r && c == node.c;
    }

    @Override
    public int hashCode() {
        return Objects.hash(r, c);
    }
}

public class AStar_gemini { // A* 算法实现 显示最短路径

    private static int heuristic(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }

    // 修改返回类型为 List<Node> 或 Map.Entry<Integer, List<Node>>
    // 这里我们返回一个包含路径长度和路径的自定义结果对象
    static class PathResult {
        int length;
        List<Node> path;

        public PathResult(int length, List<Node> path) {
            this.length = length;
            this.path = path;
        }
    }

    public static PathResult solveMaze(char[][] maze) { // 修改返回类型
        int M = maze.length;
        int N = maze[0].length;

        Node startNode = null;
        Node endNode = null;

        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (maze[r][c] == 'S') {
                    startNode = new Node(r, c, 0, 0, null);
                } else if (maze[r][c] == 'E') {
                    endNode = new Node(r, c, 0, 0, null);
                }
            }
        }

        if (startNode == null || endNode == null) {
            return null; // 或者抛出异常
        }

        startNode.hCost = heuristic(startNode.r, startNode.c, endNode.r, endNode.c);
        startNode.fCost = startNode.gCost + startNode.hCost;

        PriorityQueue<Node> openList = new PriorityQueue<>();
        HashMap<Node, Integer> gCosts = new HashMap<>();
        // 关键：现在 Node 对象内部就包含了 parent，所以 cameFrom 可以简化，
        // 或者仍然使用 HashMap<Node, Node> 来管理，取决于具体设计。
        // 这里为了演示，我们依赖 Node 内部的 parent 字段。
        // 如果 Node 是不可变的，或者需要处理优先级队列中更新节点的问题，
        // 那么一个独立的 cameFrom HashMap 依然很有用。
        // 为了和之前的代码保持一致，我们继续用 HashMap 来存储 cameFrom。
        HashMap<Node, Node> cameFrom = new HashMap<>();

        openList.add(startNode);
        gCosts.put(startNode, 0);

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!openList.isEmpty()) {
            Node current = openList.poll();

            // 如果当前节点是终点，重建并返回路径
            if (current.r == endNode.r && current.c == endNode.c) {
                List<Node> path = new ArrayList<>();
                Node temp = current;
                while (temp != null) {
                    path.add(temp);
                    temp = cameFrom.get(temp); // 从 cameFrom 中获取父节点
                }
                Collections.reverse(path); // 路径是倒序的，需要反转
                return new PathResult(current.gCost, path); // 返回路径长度和路径
            }

            for (int[] dir : directions) {
                int nr = current.r + dir[0];
                int nc = current.c + dir[1];

                if (nr < 0 || nr >= M || nc < 0 || nc >= N || maze[nr][nc] == '#') {
                    continue;
                }

                int newGCost = current.gCost + 1;
                // 这里创建一个临时的 Node 来查询 HashMap，
                // 因为 HashMap 的 equals/hashCode 只需要 r, c
                Node neighborKey = new Node(nr, nc, 0, 0, null);

                if (!gCosts.containsKey(neighborKey) || newGCost < gCosts.get(neighborKey)) {
                    // 创建一个真正要添加到openList的neighbor，并设置其parent为current
                    Node neighbor = new Node(nr, nc, newGCost, heuristic(nr, nc, endNode.r, endNode.c), current);

                    gCosts.put(neighbor, newGCost); // 这里的键是新的neighbor对象
                    openList.add(neighbor);
                    cameFrom.put(neighbor, current); // 记录是从 current 到 neighbor
                }
            }
        }
        return null; // 没有找到路径
    }
/*  输入:
5 5

S....
.#.#.
.###.
.##..
...E.
 */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入迷宫的行数 M 和列数 N (用空格分隔):");
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        scanner.nextLine();

        char[][] maze = new char[M][N];
        System.out.println("请输入迷宫的布局 (每行直接输入M个字符，不带分隔符):");
        for (int i = 0; i < M; i++) {
            maze[i] = scanner.nextLine().toCharArray();
        }

        PathResult result = solveMaze(maze); // 接收 PathResult 对象

        if (result != null) {
            System.out.println("最短路径长度: " + result.length);
            System.out.println("最短路径:");
            for (Node node : result.path) {
                System.out.println("(" + node.r + ", " + node.c + ")");
            }
        } else {
            System.out.println("无法找到路径。");
        }

        scanner.close();
    }
}